PGCD de deux entiers

Soient $a$, $b$ et $c$ trois entiers relatifs non nuls.

    Étant donnés deux entiers relatifs $a$ et $b$ dont au moins est non nul, l'ensemble des diviseurs communs à $a$ et à $b$ admet un plus grand élément, que l'on appelle le plus grand commun diviseur à $a$ et $b$ et que l'on note $PGCD(a,b)$

    Lorsque $PGCD(a,b)=1$, on dit que les entiers $a$ et $b$ sont premiers entre eux

Déterminer à l'aide de la décomposition en produit de facteur premier le $PGCD(390,525)$

Soient deux entiers relatifs $a$ et $b$ , avec $a\ne 0$, on a :

  1. $a$ étant positif, $PGCD(a,0)=a$; $PGCD(a,1)=1$
  2. $PGCD(a,b)=PGCD(|a|,|b|)$.
  3. Si $b$ divise $a$, $PGCD(a,b)=|b|$
  4. Si $b$ est premier et ne divise pas $a$, $PGCD(a,b)=1$

Démontrer la propriété précédente.

Soient $a$ et $b$ deux entiers naturels non nuls avec $b<a$.
On appelle $r$ le reste de la division euclidienne de $a$ par $b$. $$PGCD(a,b)=PGCD(b,r)$$

Démonstration de $PGCD(a,b)=PGCD(b,r)$
Pour démontrer cette propriétés, nous devons montrer que $\{d \in\mathbb{N}$, $d|a$ et $d|b\}=\{d \in\mathbb{N}$, $d|b$ et $d|r\}$. Autrement dit l'ensemble des diviseurs de $a$ et de $b$ sont aussi les diviseurs de $b$ et de $r$

Algorithme d'Euclide

Cette dernière propriété permet de mettre en place une procédure pour déterminer le PGCD de deux entiers c'est l'algorithme d'Euclide.

Appliquer l'algorithme d'Euclide pour déterminer le PGCD de $7260$ et de $1107$

Écrire une fonction euclide en Python qui prend comme argument deux entiers $a$ et $b$ et qui renvoie le PGCD de $a$ et de $b$.

Homogénéité

Soient trois entiers naturels $a$, $b$, et $k$. $$PGCD(ka,kb)=k\times PGCD(a,b).$$

$D=PGCD(a,b)$ et $D'=PGCD(ka,kb)$.

Démonstration de l'homogénéité du PGCD

  • Première étape : Montrer que $kD\leq D'$
  • Deuxième étape : Montrer que $D'\leq kD$ On pourra commencer par montrer que $k|D'$
  • Je vous laisse le plaisir d'essayer !!

    • Soient $a$ et $b$ deux entiers naturels.
    $d=PGCD(a,b)$ si, et seulement si $\frac{a}{D}$ et $\frac{b}{D}$ sont des entiers premiers entre eux.

    Démonstration de $D=PGCD(a,b)$ si, et seulement si $\frac{a}{D}$ et $\frac{b}{D}$ sont des entiers premiers entre eux.
    Soient $a$ et $b$ deux entiers naturels non nuls.

    1. On note $D=PGCD(a,b)$.
      1. Justifier que $\frac{a}{D}$ et $\frac{b}{D}$ sont des entiers naturels non nuls.
      2. On note $d=PGCD(\frac{a}{D},\frac{b}{D})$. En utilisant la propriété d'homogénéité montrer que $d=1$
    2. Réciproquement on suppose que $\frac{a}{D}$ et $\frac{b}{D}$ sont premiers entre eux.
      Montrer que $PGCD(a,b)=D$

    Exercices

    Calculer le PGCD des nombres suivants :

    1. $a=826$ et $b=644$
    2. $a=1210$ et $b=308$
    3. $a=3256$ et $b=-2354$

    A l'aide du PGCD donner la version irréductible de ces fractions :

    1. $\frac{1864}{1631}$
    2. $\frac{3103650}{3420}$

    Soient $a=n$ et $b=n+1$, $a$, $n$ est un entier naturel.

    1. Montrer que si $d$ divise $a$ et $b$ alors $d=1$
    2. En déduire que $a$ et $b$ sont premier entre eux.

    Même énoncé avec $a=n+1$ et $b=2n+1$

    Soit $n$ un entier naturel non nul. En utilisant l'algorithme d'Euclide, démontrer que les entiers $a$ et $b$ sont premiers entre eux.

    1. $a=3n+2$ et $b=n+1$
    2. $a=5n+7$ et $b=2n+3$
    3. $3n^2+5n+1$ et $b=3n+1$

    Calculer les valeurs de $a$ et $b$ possibles sachant que $a+b=360$ et $PGCD(a,b)=18$.

    Calculer les valeurs de $a$ et $b$ possibles sachant que $a-b=105$ et $PGCD(a,b)=15$ et que $a$ et $b$ sont inférieurs à 300.

    Calculer les valeurs de $a$ et $b$ possibles sachant que $ab=1734$ et $PGCD(a,b)=17$.

    Soient $a$ et $b$ deux entiers relatifs non nuls et $n$ un entier naturel non nul.

    1. On suppose que $a\equiv b [n]$. Montrer que le $PGCD(a,n)=PGCD(b,n)$
    2. Montrer que la réciproque est fausse.